package 我的Java学习_算法基础.day_05;

import java.util.Arrays;

public class _079_最短摘要的生成 {
    public static void main(String[] args) {
        solve(new String[]{"a","b","c","d","h","e","f","c","c","d","e","f","d","c"},new String[]{"c","e"});
    }
    static void solve(String[] w,String[] keys){
        //begin、end用于在找到更短的包含全部关键字的子数组时更新
        int begin = -1;
        int end = -1;
        int p2=-1;  //记录上次j的位置
        
        int len = Integer.MAX_VALUE;
        int[] keyFound = new int[keys.length];
        for(int i=0;i<w.length;i++){
            Arrays.fill(keyFound,0);
            //如果I位置是关键字，求以I开头包含所有关键字的序列
            String word1 = w[i];
            int index = indexOf(keys,word1);
            if(index==-1){
                continue;
            }else{
                keyFound[index]=1;//标记
            }
            int j;
            if(p2!=-1)
                j=p2;
            else
                j=i+1;
            for(;j<w.length;j++){
                String word2 = w[j];
                int index1 = indexOf(keys,word2);
                if(index1==-1||keyFound[index1]==1){
                    continue;
                }else {//找到没有发现过的关键字
                    keyFound[index1]=1;
                    if(sum(keyFound)==keys.length){//全部找到
                        p2=j;
                        if(j-i+1<len){
                            len = j - i+1;
                            begin = i;
                            end = j;
                        }
                        break;
                    }
                }

            }
        }
        print(w,begin,end);
    }

    private static void print(String[] w, int begin, int end) {
        System.out.println(begin+" "+end);
        for(int i =begin;i<=end;i++){
            System.out.print(w[i]+" ");
        }
        System.out.println();
    }

    private static int sum(int[] keyFound) {
        int sum=0;
        for(int i =0;i<keyFound.length;i++){
            sum+=keyFound[i];
        }
        return sum;
    }

    /**
     * word在keys数组的第几位
     * @param keys 关键字数组
     * @param word1
     * @return
     */
    private static int indexOf(String[] keys, String word1) {
        for(int i =0;i<keys.length;i++){
            if(keys[i].equals(word1)){
                return i;
            }
        }
        return -1;
    }
}
